// Vertex Class implementation
#include "Vertex.h"
#include "VertexDirectory.h"
#include "Helpers.h"
#include "Group.h"
#include "RankSet.h"
#include <iostream>
#include <ctime>
using namespace std;

//-----------------------------------------------------------------------------------------
// Public
//-----------------------------------------------------------------------------------------

//-----------------------------------------------------------------------------------------
//ctor
//-----------------------------------------------------------------------------------------
Vertex::Vertex(VertexKey vertexName, VertexDirectory* dir)
{
	m_VertexName = vertexName;
	m_Rank = 0; 
	// on initialization, the vertex is in the graph
	m_InGraph = true;
	m_Directory = dir;
	// when initialized, these fields are false, but are automatically intialized to true by the copmiler,
	// so we initialize specifically
	m_IsReplacement = false;
	m_Interchangeable = false;
	m_CurrentContainer = NULL;
	m_InterchangableContainer = NULL;
	m_ContainingVertexSet = NULL;
	m_VertexWeight = CalcWeight(vertexName);
	CreateNeighbours();
}

//-----------------------------------------------------------------------------------------
//dtor
//-----------------------------------------------------------------------------------------
Vertex::~Vertex()
{
	if (m_NeighboursInGraph.empty() == false)
	{
		set<VertexKey >::iterator it;
		for (it = m_NeighboursInGraph.begin(); it != m_NeighboursInGraph.end(); it++)
		{
			(*it).~vector();
		}
	}
	if (m_NeighboursNotInGraph.empty() == false)
	{
		set<VertexKey >::iterator it;
		for (it = m_NeighboursNotInGraph.begin(); it != m_NeighboursNotInGraph.end(); it++)
		{
			(*it).~vector();
		}
	}
	m_VertexName.~vector();
}


//-----------------------------------------------------------------------------------------
// Copy 
// copies all the data from vertexToCopy into this vertex instance
//-----------------------------------------------------------------------------------------
void Vertex::Copy(Vertex* vertexToCopy)
{
	this->m_VertexName = VertexKey(vertexToCopy->Name());
	this->m_Rank = vertexToCopy->Rank(); 
	this->m_InGraph = vertexToCopy->IsInGraph();
	this->m_IsReplacement = vertexToCopy->IsReplacement();
	this->m_Interchangeable = vertexToCopy->Interchangeable();
	this->m_CurrentContainer = vertexToCopy->GetContainer();
	this->m_ContainingVertexSet = vertexToCopy->GetContainingVertexSet();
	this->m_VerticesToReplace = set<VertexKey>(vertexToCopy->GetInterchangeables());
	this->m_Replacements = set<VertexKey>(vertexToCopy->GetReplacements());
	this->m_InterchangableContainer = vertexToCopy->GetPreviousContainer();
	this->m_VertexWeight = CalcWeight(vertexToCopy->Name());
	this->m_NeighboursInGraph = set<VertexKey>(vertexToCopy->GetNeighboursInGraph());
	this->m_NeighboursNotInGraph = set<VertexKey>(vertexToCopy->GetNeighboursNotInGraph());	
}

//-----------------------------------------------------------------------------------------
// Name: Returns the vertex name (VertexKey)
//-----------------------------------------------------------------------------------------
const VertexKey Vertex::Name()
{
	return m_VertexName;
}

//-----------------------------------------------------------------------------------------
// Rank: Returns the count of the number of neighbours this vertex has, that are still 
// in the graph
//-----------------------------------------------------------------------------------------
long Vertex::Rank()
{
	return m_Rank;
}

//-----------------------------------------------------------------------------------------
// UpdateRank: Change rank by parameter
// Parameters:
// modifer - by how much to change the rank
//-----------------------------------------------------------------------------------------
void Vertex::UpdateRank(long modifier)
{
	m_Rank+=modifier;
}

//-----------------------------------------------------------------------------------------
// Opertaor== : Compare by name
//-----------------------------------------------------------------------------------------
bool Vertex::operator==(Vertex &otherVertex)
{
	return (otherVertex.Name() == this->Name());	
}

//-----------------------------------------------------------------------------------------
// Opertaor!= : Compare by name
//-----------------------------------------------------------------------------------------
bool Vertex::operator!=(Vertex &otherVertex)
{
	return !((*this) == otherVertex);
}

//-----------------------------------------------------------------------------------------
// IsIterchangeable: Can this vertex be replaced with another vertex from the graph (not a
// group)
//-----------------------------------------------------------------------------------------
bool Vertex::Interchangeable()
{
	return m_Interchangeable;
}


//-----------------------------------------------------------------------------------------
// IsReplacement: Can this vertex replace another vertex in some grop
//-----------------------------------------------------------------------------------------
bool Vertex::IsReplacement()
{
	return m_IsReplacement;
}

//-----------------------------------------------------------------------------------------
// IsInGraph: is this vertex in the graph or not
//-----------------------------------------------------------------------------------------
bool Vertex::IsInGraph()
{
	return m_InGraph;
}

//-----------------------------------------------------------------------------------------
// Neighbours: returns true iff otherVertex is a neighbour of this vertex
// (in the graph or not in the graph)
//-----------------------------------------------------------------------------------------
bool Vertex::Neighbours(VertexBase* otherVertex)
{
	return (NeighboursInGraph(otherVertex) || NeighboursNotInGraph(otherVertex));
}

//-----------------------------------------------------------------------------------------
// NeighboursInGraph: returns true iff otherVertex is a neighbour of this vertex, in the graph
//-----------------------------------------------------------------------------------------
bool Vertex::NeighboursInGraph(VertexBase* otherVertex)
{
	set<VertexKey >::iterator it;
	it = m_NeighboursInGraph.find(((Vertex*)otherVertex)->Name());
	if (it == m_NeighboursInGraph.end())
	{
		return false;
	}
	return true;
}

//-----------------------------------------------------------------------------------------
// NeighboursNotInGraph: returns true iff otherVertex is a neighbour of this vertex,
//                       not in the graph
//-----------------------------------------------------------------------------------------
bool Vertex::NeighboursNotInGraph(VertexBase* otherVertex)
{
	set<VertexKey >::iterator it;
	it = m_NeighboursNotInGraph.find(((Vertex*)otherVertex)->Name());
	if (it == m_NeighboursNotInGraph.end())
	{
		return false;
	}
	return true;
}
	
//-----------------------------------------------------------------------------------------
// GetVertexDirectory: Returns the vertex directory associated with this vertex
//-----------------------------------------------------------------------------------------
VertexDirectory* Vertex::GetVertexDirectory()
{
	return m_Directory;
}

//-----------------------------------------------------------------------------------------
// GetContainingGraph: Returns the graph this vertex belongs to or NULL if it is in a group
//-----------------------------------------------------------------------------------------
Graph *Vertex::GetContainingGraph()
{
	if (!m_InGraph)
	{
		return NULL;
	}

	RankSet* rankSet = dynamic_cast<RankSet*>(m_CurrentContainer);
	Graph *graph;
	if (rankSet == NULL)
	{
		// try temp set
		TempVertexContainer *tempSet = static_cast<TempVertexContainer*>(m_CurrentContainer);
		if (tempSet == NULL)
		{
			throw new GraphColoringException("Vertex is in graph but container is not a graph container");
		}
		graph = tempSet->GetContainingGraph();
	} else
	{
		graph = rankSet->GetContainingGraph();
	}
	return graph;
}
//-----------------------------------------------------------------------------------------
// GetContainingVertexSet: Returns the vertex set associated with this vertex
//-----------------------------------------------------------------------------------------
VertexSet* Vertex::GetContainingVertexSet()
{
	return m_ContainingVertexSet;
}

//-----------------------------------------------------------------------------------------
// SetContaingVertexSet: set the vertex set associated with this vertex
//-----------------------------------------------------------------------------------------
void Vertex::SetContaingVertexSet(VertexSet *vertexSet)
{
	m_ContainingVertexSet = vertexSet;
}

//-----------------------------------------------------------------------------------------
// ClearInterchangeableInformation: clears all information related to switching
//-----------------------------------------------------------------------------------------
void Vertex::ClearInterchangeableInformation()
{
	m_IsReplacement = false;
	m_Interchangeable = false;
	m_Replacements.clear();
	m_VerticesToReplace.clear();
	m_InterchangableContainer = NULL;
	m_ContainingVertexSet = NULL;
}

//-----------------------------------------------------------------------------------------
// MoveToContainer: move the vertex to OtherContainer container.
// Parameters:
// otherContainer - where to
// vertexInGraph marks if after the change the vertex should be in the graph (since the move 
// can be from a bucket in the graph to a group or vica-versa, or between 2 groups\buckets)
// updateNeighbours - if false neighbours are not updated of this change (default: true)
//-----------------------------------------------------------------------------------------
void Vertex::MoveToContainer(VertexContainer* otherContainer, bool vertexInGraph, bool updateNeighbours)
{
	VertexContainer* container = otherContainer;
	if (otherContainer != NULL && container == NULL)
	{
		throw new GraphColoringException("Trying to move vertex to something that ins't a container");
	}
	m_CurrentContainer = container;

	if (updateNeighbours && m_InGraph != vertexInGraph)
	{ // moving the vertex from the graph to a group or visa-versa - need to update all its neighbours
		UpdateNeighbours(vertexInGraph, m_NeighboursInGraph);
		UpdateNeighbours(vertexInGraph, m_NeighboursNotInGraph);
	}
	m_InGraph = vertexInGraph;
}


//-----------------------------------------------------------------------------------------
// MoveToContainer: move the vertex to OtherContainer container.
// Parameters:
// otherContainer - where to
// vertexInGraph marks if after the change the vertex should be in the graph (since the move 
// can be from a bucket in the graph to a group or vica-versa, or between 2 groups\buckets)
//-----------------------------------------------------------------------------------------
void Vertex::MoveToContainer(VertexContainer* otherContainer, bool vertexInGraph)
{
	MoveToContainer(otherContainer, vertexInGraph, true);
}

//-----------------------------------------------------------------------------------------
// GetContainer: returns the group/bucket this vertex is a member of
//-----------------------------------------------------------------------------------------
VertexContainer* Vertex::GetContainer()
{
	return m_CurrentContainer;
}

//-----------------------------------------------------------------------------------------
// GetPreviousContainer
// is used for interchangeable vertices. In this case the vertex is returned to the graph,
// and this method will return the group the vertex was in when set as interchangable
//-----------------------------------------------------------------------------------------
VertexContainer* Vertex::GetPreviousContainer()
{
	return m_InterchangableContainer;
}


//-----------------------------------------------------------------------------------------
// ResetContainer: Moves the vertex to no container (and out of the graph)
//-----------------------------------------------------------------------------------------
void Vertex::ResetContainer()
{
	MoveToContainer(NULL,false);
}

//-----------------------------------------------------------------------------------------
// GetReplacements: Returns all vertices that can replace this vertex
//-----------------------------------------------------------------------------------------
set<VertexKey> Vertex::GetReplacements()
{
	return m_Replacements;
}

//-----------------------------------------------------------------------------------------
// GetInterchangeables: Returns all vertices that can be replaced by this vertex
//-----------------------------------------------------------------------------------------
set<VertexKey> Vertex::GetInterchangeables()
{
	return m_VerticesToReplace;
}

//-----------------------------------------------------------------------------------------
// GetInterchangeables: Returns all vertices that can be replaced by this vertex (pointers)
//-----------------------------------------------------------------------------------------
set<Vertex *> Vertex::GetInterchangeableVertices()
{
	set<Vertex*> returnSet;
	set<VertexKey>::iterator it;
	for (it = m_VerticesToReplace.begin(); it != m_VerticesToReplace.end(); it++)
	{
		Vertex *interchangeable = GetVertexFromRightDirectory(*it);
		if (interchangeable != this && interchangeable->Interchangeable() && interchangeable->IsInGraph() && returnSet.find(interchangeable)==returnSet.end())
		{
			returnSet.insert(interchangeable);
		}
	}

	return returnSet;
}

//-----------------------------------------------------------------------------------------
// FindReplacements: Go over the vertex's neighbours in the graph and see which of them can
// replace it in its current group. Fills the m_Replacements set.
// Vertex must belong to some group.
//-----------------------------------------------------------------------------------------
void Vertex::FindReplacements(Graph *graph)
{
	if (m_InGraph)
	{
		throw new GraphColoringException("Trying to find replacements for a vertex in the rest of graph (not a group)");
	}

	Group *group = dynamic_cast<Group*>(m_CurrentContainer);
	set<VertexKey>::iterator it;
	// Remove vertex from its current group so we can check if it is legal to replace it
	group->RemoveVertex(this);
	
	// Go over all neighbours and look for replacements
	set<VertexKey> neighboursCopy(m_NeighboursInGraph);
	for (it = neighboursCopy.begin(); it != neighboursCopy.end(); it++)
	{
		Vertex *neighbour = GetVertexFromRightDirectory(*it);
		if (!neighbour->HasNeighbourInGroup(group))
		{	
			// Return vertex to current group
			group->InsertNewVertex(this);
			Vertex::CreateInterchangeableLink(this,neighbour);
			// Remove vertex from its current group so we can check if it is legal to replace it
			group->RemoveVertex(this);
		}
	}

	// Return vertex to current group
	group->InsertNewVertex(this);
}

//-----------------------------------------------------------------------------------------
// SetInterchangeable: Mark this vertex as interchangeable (can be replaced by another vertex)
// this operation is allowed only if the vertex is not currently in the
// graph (e.g. it is a member of a group).
// otherwise, the method returns 1 (error) and does nothing
// returns: 0 in case of success (vertex not in graph), 1 otherwise
//-----------------------------------------------------------------------------------------
void Vertex::SetInterchangeable(VertexBase* otherVertex, bool updateContainer)
{
	if (updateContainer)
	{
		if (m_InGraph)
		{
			// Error! This vertex is in the graph
			throw new GraphColoringException("Trying to set a vertex in the graph (not group) as interchangeable");
		}

		m_InterchangableContainer = m_CurrentContainer;
	}
	m_Interchangeable = true;
	// NULL - used as interchangeable pair
	if (otherVertex != NULL)
	{
		Vertex *vertex = dynamic_cast<Vertex*>(otherVertex);
		if (m_Replacements.find(vertex->Name()) == m_Replacements.end())
		{
			m_Replacements.insert(vertex->Name());	
		}
	}
}


//-----------------------------------------------------------------------------------------
// ResetInterchangeableWithVertex: remove a vertex from the list of vertices that can replace 
// this vertex
//-----------------------------------------------------------------------------------------
void Vertex::ResetInterchangeableWithVertex(Vertex* otherVertex)
{
	
	set<VertexKey>::iterator it;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		if (*it==otherVertex->Name())
		{
			m_Replacements.erase(it);
			return;
		}
	}

	// An interchangeable vertex dosn't stop being one when it runs out of replacements, do not update flag!
}

//-----------------------------------------------------------------------------------------
// ResetInterchangeable: mark this vertex as not interchangeable - will be useful at the end 
// of iterations, when we want to reset the status of all the vertices
//-----------------------------------------------------------------------------------------
void Vertex::ResetInterchangeable()
{
	RemoveAllReplacements();
	m_Interchangeable = false;
	m_Replacements.clear();
	m_InterchangableContainer = NULL;
}


//-----------------------------------------------------------------------------------------
// SetAsReplacementFor: mark this vertex as a possible replacement for otherVertex
// returns: 0 in case of success (vertex in graph), 1 otherwise
//-----------------------------------------------------------------------------------------
void Vertex::SetAsReplacementFor(VertexBase* otherVertex)
{
	m_IsReplacement = true;
	// NULL - used in as a pair replacement
	if (otherVertex != NULL)
	{
		Vertex *vertex = dynamic_cast<Vertex*>(otherVertex);
		if (m_VerticesToReplace.find(vertex->Name()) == m_VerticesToReplace.end())
		{
			m_VerticesToReplace.insert(vertex->Name());
		}
	}
}

//-----------------------------------------------------------------------------------------
// ResetReplacementForVertex: remove a vertex from the list of vertices that this vertex can replace
//-----------------------------------------------------------------------------------------
void Vertex::ResetReplacementForVertex(Vertex* otherVertex)
{
	set<VertexKey>::iterator it;
	for (it = m_VerticesToReplace.begin(); it != m_VerticesToReplace.end(); it++)
	{
		if (*it==otherVertex->Name())
		{
			m_VerticesToReplace.erase(it);
			if (m_VerticesToReplace.empty())
			{
				m_IsReplacement = false;
			}
			return;
		}
	}	
}

//-----------------------------------------------------------------------------------------
// ResetIsReplacement: mark this vertex as not a replacement - will be useful at the end of 
// iterations, when we want to reset the status of all the vertices
//-----------------------------------------------------------------------------------------
void Vertex::ResetIsReplacement()
{
	SetReplacementFlag(false);
	set<VertexKey>::iterator it;
	for (it = m_VerticesToReplace.begin(); it != m_VerticesToReplace.end(); it++)
	{
		Vertex *otherVertex= GetVertexFromRightDirectory(*it);
		// Remove this vertex from the other's list
		if (otherVertex->Interchangeable())
		{
			otherVertex->ResetInterchangeableWithVertex(this);
		}
	}
	m_VerticesToReplace.clear();
}


//-----------------------------------------------------------------------------------------
// CanBeReplaced: returns true if this vertex is iterchangeable and has a replacement vertex
// that can be added to the vertex's original group (we can switch them) 
//-----------------------------------------------------------------------------------------
bool Vertex::CanBeReplaced()
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Calling CanBeReplaced on non-interchangeable vertex");
	}


	// Assuming this is correct - this container is the copy one
	Group *group = dynamic_cast<Group*>(m_InterchangableContainer);
	if (group == NULL)
	{
		throw new GraphColoringException("Interchangeable container is not a group!");
	}

	// Check if there is a replacement vertex that works as a replacement
	set<VertexKey>::iterator it;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		// Try to replace and see that all interchangeables are still OK
		Vertex *replacement = GetVertexFromRightDirectory(*it);
		if (!replacement->IsReplacement())
		{
			continue;
		}

		if (!replacement->IsInGraph())
		{
			continue;
		}
		
		if (!group->IsLegalToAdd(replacement))
		{
			continue;
		}

		
		// See what happens after replacing
		ReplaceWith(replacement,GetContainingGraph(), false);
		
		bool interchangeablesState = replacement->CanAllRelatedInterchangeablesBeReplaced();

		replacement->UndoReplacementWith(this, true);

		// If this is a combination that works, this vertex can be replaced
		if (interchangeablesState = true)
		{
			Debug::PrintDebugMsg(this->PrintName() + " can be replaced by " + replacement->PrintName());
			if (!replacement->IsReplacement())
			{
				Debug::PrintDebugMsg("Which is not a replacement");
				replacement->SetAsReplacementFor(this);
				Debug::PrintDebugMsg("but is now!");
			}
			return true;
		}
	}
	Debug::PrintDebugMsg(this->PrintName() + " cannot be replaced");
	return false;
}

//-----------------------------------------------------------------------------------------
// CanReturnToOriginalGroup: returns true if this is an interchangeable vertex that
// can be returned to its original group
//-----------------------------------------------------------------------------------------
bool Vertex::CanReturnToOriginalGroup()
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Calling CanBeReplaced on non-interchangeable vertex");
	}

	// Assuming this is correct - this container is the copy one
	Group *group = dynamic_cast<Group*>(m_InterchangableContainer);
	
	SetInterchangeableFlag(false);
	bool canReturn = group->IsLegalToAdd(this, true);
	SetInterchangeableFlag(true);
	return canReturn;
}

//-----------------------------------------------------------------------------------------
// CanBeRemovedFromReplacements: returns true if after removing this vertex from the 
// replacements list for all the interchangeable vertices
// it belongs to they can all still be replaced or moved back
// to their original group
//-----------------------------------------------------------------------------------------
bool Vertex::CanBeRemovedFromReplacements()
{
	if (!m_IsReplacement)
	{
		throw new GraphColoringException("Calling CanBeRemovedFromReplacements on non-replacement vertex");
	}

	set<VertexKey>::iterator it;
	// Stop being a replacement
	SetReplacementFlag(false);

	set<VertexKey> verticesToCheck(m_VerticesToReplace);

	for (it = verticesToCheck.begin(); it != verticesToCheck.end(); it++)
	{
		bool legal = true;
		Vertex *interchangeableVertex = GetVertexFromRightDirectory(*it);

		if (!interchangeableVertex->Interchangeable())
		{
			continue;
		}
		
		if (!interchangeableVertex->CanReturnToOriginalGroup() && !interchangeableVertex->CanBeReplaced())
		{
			legal = false;
		}

		if (!legal)
		{
			// Return this vertex to replacement lists
			SetReplacementFlag(true);
			return false;
		}
	}
	
	// Return this vertex to replacement lists
	SetReplacementFlag(true);
	return true;
}

//-----------------------------------------------------------------------------------------
// UpdateReplacementState: Checks if this vertex (marked as replacement) can still replace
// all the interchangeable vertices it belongs to
//-----------------------------------------------------------------------------------------
void Vertex::UpdateReplacementState()
{
	if (!m_IsReplacement)
	{
		// If this vertex is not a replacement, stop now
		return;
	}
	
	set<VertexKey>::iterator it;
	set<VertexKey> verticesToReplaceCopy(m_VerticesToReplace);
	for (it = verticesToReplaceCopy.begin(); it!= verticesToReplaceCopy.end(); it++)
	{
		Vertex *interchangeableVertex = GetVertexFromRightDirectory(*it);
		// Check if vertex is still relevant
		if (!interchangeableVertex->Interchangeable())
		{
			continue;
		}

		Group *group = dynamic_cast<Group*>(interchangeableVertex->GetPreviousContainer());
		// If we can't add this vertex to the interchangeable one's original group
		// it shouldn't be marked like one any more
		if (!this->IsInGraph() || !group->IsLegalToAdd(this, true))
		{
			string message = "Vertex ";
			message.append(PrintName());
			message.append(" is no longer a legal replacement");
			message.append(" for ");
			message.append(interchangeableVertex->PrintName());
			Debug::PrintDebugMsg(message);

			interchangeableVertex->ResetInterchangeableWithVertex(this);
			this->ResetReplacementForVertex(interchangeableVertex);
			continue;
		}
		
	}
}

//-----------------------------------------------------------------------------------------
// UpdateReplacementStateForAllNeighboursInGraph: Goes over all of this vertex's neighbours
// in the graph and checks if they are still valid replacements. If not, removes them from
// all lists
//-----------------------------------------------------------------------------------------
void Vertex::UpdateReplacementStateForAllNeighboursInGraph()
{
	set<VertexKey>::iterator it;
	set<VertexKey> neighboursInGraph(m_NeighboursInGraph);
	for (it = neighboursInGraph.begin(); it != neighboursInGraph.end() ; it++)
	{
		Vertex *vertex = GetVertexFromRightDirectory(*it);
		vertex->UpdateReplacementState();		
	}
}

//-----------------------------------------------------------------------------------------
// CanAllNeighboursInterchangeablesBeReplaced:
// Goes over all neighbours' interchangeable vertices and checks they are still replaceable
// returns false if not
//-----------------------------------------------------------------------------------------
bool Vertex::CanAllRelatedInterchangeablesBeReplaced()
{
	// Combine this vertex's interchangeables with it's neighbours' ones
	set<Vertex*> replacementsToCheck = GetInterchangeableVertices();
	set<Vertex *> neighboursInterchangeables = GetAllRelatedInterchangeables();
	set<Vertex*>::iterator it;
	for (it = neighboursInterchangeables.begin(); it != neighboursInterchangeables.end(); it++)
	{
		if (replacementsToCheck.find(*it) == replacementsToCheck.end())
		{
			replacementsToCheck.insert(*it);
		}
	}

	return CanWholeListBeReplaced(replacementsToCheck);
}

//-----------------------------------------------------------------------------------------
// CanAllVerticesToReplaceBeReplaced:
// Goes over all vertices this one replaces and checks they are still replaceable
// returns false if not
//-----------------------------------------------------------------------------------------
bool Vertex::CanAllVerticesToReplaceBeReplaced()
{
	set<Vertex*> relatedInterchangeables = GetInterchangeableVertices();
	if (relatedInterchangeables.size() == 0)
	{
		return true;
	}
	return CanWholeListBeReplaced(relatedInterchangeables);
	
}
//-----------------------------------------------------------------------------
// HasNeighbourInGroup Returns true if vertex has a neighbour in the group
//-----------------------------------------------------------------------------
bool Vertex::HasNeighbourInGroup(Group *group)
{
	set<VertexKey>::iterator it; 
	for(it = m_NeighboursNotInGraph.begin();it != m_NeighboursNotInGraph.end(); it++)
	{
		if (group->IsVertexInGroup(*it))
			return true;
	}
	return false;
}


//-----------------------------------------------------------------------------
// Replace: Replaces current interchangeable vertex with one of it's replacements
// (Puts it in the original group)
//-----------------------------------------------------------------------------
void Vertex::Replace(Graph *graph)
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Trying to replace a non-interchangeable vertex");
	}

	Vertex *replacement = GetLegalReplacementVertex();
	if (replacement == NULL)
	{
		throw new GraphColoringException("No replacement available for "+PrintName());
	}
	
	ReplaceWith(replacement, graph, true);
}

//-----------------------------------------------------------------------------------------
// ReturnToOriginalContainer: returns the vertex to its original container
// assumes vertex is not in graph any more
//-----------------------------------------------------------------------------------------
void Vertex::ReturnToOriginalContainer(bool updateLists)
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Trying to return non-interchangeable vertex to it's original group");
	}

	Group *group = dynamic_cast<Group*>(m_InterchangableContainer);
	if (group == NULL)
	{
		throw new GraphColoringException("Original container is not a group, can't return to it");
	}

	group->InsertNewVertex(this);
	SetInterchangeableFlag(false);

	if (updateLists)
	{
		ResetInterchangeable();
	}
}

//-----------------------------------------------------------------------------------------
// RemoveAllReplacements: Updates all replacement vertices that this vertex isn't 
// interchangeable anymore
//-----------------------------------------------------------------------------------------
void Vertex::RemoveAllReplacements()
{
	set<VertexKey>::iterator it;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		Vertex *replacement = GetVertexFromRightDirectory(*it);
		replacement->ResetReplacementForVertex(this);
	}

	m_Replacements.clear();
}

//-----------------------------------------------------------------------------------------
// UndoReplacement: puts a replacement vertex back in the graph
//-----------------------------------------------------------------------------------------
void Vertex::UndoReplacementWith(Vertex *otherVertex, bool returnToGraph)
{
	Group *group = dynamic_cast<Group*>(m_CurrentContainer);
	if (group == NULL)
	{
		throw new GraphColoringException("Undoing replacement for vertex that isn't in group");
	}

	Graph *graph = otherVertex->GetContainingGraph();

	group->RemoveVertex(this);
	if (returnToGraph)
	{
		graph->InsertVertex(this);
	} else
	{	
		ResetContainer();
	}

	// Update flags
	otherVertex->SetInterchangeableFlag(true);
	SetReplacementFlag(true);
}

//-----------------------------------------------------------------------------------------
// ReplaceWith: Put replacementVertex in this vertex's original group
// this method is only allowed on interchangeable vertices
//-----------------------------------------------------------------------------------------
void Vertex::ReplaceWith(Vertex *replacementVertex, Graph *graph, bool updateLists) 
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Trying to replace a vertex that isn't interchangeable");
	}

	Group *group = dynamic_cast<Group*>(m_InterchangableContainer);
	if (group == NULL)
	{
		throw new GraphColoringException("Could not get interchangeable container from pointer");
	}

	if (replacementVertex->IsInGraph() && graph != NULL)
	{
		graph->RemoveVertex(replacementVertex);
	}

	group->InsertNewVertex(replacementVertex);

	// Clear flags
	SetInterchangeableFlag(false);
	replacementVertex->SetReplacementFlag(false);

	if (updateLists)
	{
		// Update all lists
		// This vertex is no longer interchangeable, remove it from all lists
		ResetInterchangeable();
		// The replacement is no longer a replacement, remove it from all lists
		replacementVertex->ResetIsReplacement();
	}
}

//-----------------------------------------------------------------------------------------
// GetLegalReplacementVertex: Gets a the chosen replacement vertex (chooses one if needed)
// or NULL if none available
//-----------------------------------------------------------------------------------------
Vertex *Vertex::GetLegalReplacementVertex()
{
	if (!m_Interchangeable)
	{
		throw new GraphColoringException("Getting replacement for non-interchangeable vertex");
	}

	Group *group = dynamic_cast<Group*>(this->GetPreviousContainer());
	if (group == NULL)
	{
		throw new GraphColoringException("Could not get vertex's original group");
	}

	int replacementCount = 0;
	set<VertexKey>::iterator it;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		Vertex *replacement = GetVertexFromRightDirectory(*it);
		if (replacement->IsReplacement() && replacement->IsInGraph() && group->IsLegalToAdd(replacement,false))
		{
			replacementCount++;
		}
	}

	if (replacementCount == 0)
	{
		string message = PrintName();
		message.append(" has no legal replacement!");
		Debug::PrintDebugMsg(message);
		return NULL;
	}
	
	srand((unsigned)time(0));
	// Get a random index between 0 and max index (inclusive)
	long randomIndex = rand() % (replacementCount); 
	int counter = 0;
	for (it = m_Replacements.begin(); it != m_Replacements.end(); it++)
	{
		Vertex *replacement = GetVertexFromRightDirectory(*it);
		if (replacement->IsReplacement() && replacement->IsInGraph() && group->IsLegalToAdd(replacement,false))
		{
			if (counter == randomIndex)
			{
				return replacement;
			} else
			{
				counter++;	
			}	
		}
	}

	return NULL;
}


//-----------------------------------------------------------------------------------------
// PrintName: returns the vertexName as a string - used to print the vertex name
//-----------------------------------------------------------------------------------------
string Vertex::PrintName()
{
	string name;
	for (unsigned int i=0; i< m_VertexName.size(); i++)
	{
		if (m_VertexName[i] == 0)
		{
			name.append("0");
		}
		else
		{
			name.append("1");
		}
	}
	return name;
}

//-----------------------------------------------------------------------------------------
// RemoveNeighbour: removes a neighbour of this vertex from the graph: decreeses rank and moves the nieghbour to the 
// list of neighbours not in the graph
// if the neighbour isn't a valid neighbour (valid neighbour's name differs in exactly 2 coordinates from this vertex's name)
// then the method reports error and does nothing.
// otherwise, after the method is called: nieghbour will appear in the NieghboursNotInGraph set, will not appear in
// the NieghboursInGraph set (rank updated if it was removed from the list).
// The method expects the neoghbour to be in the NieghbourInGraph set and not in the neighboursNotInGraph set
// otherwise it will print a warning but the result of the method call is the same.
// if silentMode == true then warnings are not printed
//-----------------------------------------------------------------------------------------
void Vertex::RemoveNeighbour(Vertex* neighbour, bool silentMode)
{
	set<VertexKey >::iterator it = m_NeighboursNotInGraph.find(neighbour->Name());
	if (it == m_NeighboursNotInGraph.end())
	{ // if the vertex doesn't already exist in the set - add it
		m_NeighboursNotInGraph.insert(m_NeighboursNotInGraph.begin(), neighbour->Name());
	}
	else 
		if (!silentMode)
		{
			string str = "Warning: Vertex " + neighbour->PrintName();
			str += " was already a neighbour of vertex " + this->PrintName();
			str += " not in the graph";
			Debug::PrintDebugMsg(str);
		}
	it = m_NeighboursInGraph.find(neighbour->Name());
	if (it == m_NeighboursInGraph.end())
	{ // if the neighbour isn't in the neighbours in graph set - report error
		if (!silentMode)
		{
			string str = "Warning: Vertex " + neighbour->PrintName();
			str += " not a neighbour of vertex " + this->PrintName();
			str += " in the graph";
			Debug::PrintDebugMsg(str);
		}
		return;
	}
	m_Rank--;
	m_NeighboursInGraph.erase(it);
}	

//-----------------------------------------------------------------------------------------
// AddNeighbour: adds a valid neighbour of this vertex to the graph: increeses rank and moves the neighbour to the 
// list of neighbours in the graph
// if the neighbour isn't a valid neighbour (valid neighbour's name differs in exactly 2 coordinates from this vertex's name)
// then the method reports error and does nothing.
// otherwise, after the method is called: neighbour will appear in the NeighboursInGraph set (rank updated if it was Added to the list), 
// will not appear in the NeighboursNotInGraph set.
// The method expects the neighbour to be in the NeighbourNotInGraph set and not in the neighboursInGraph set
// otherwise it will print a warning but the result of the method call is the same.
// if silentMode == true then warnings are not printed
//-----------------------------------------------------------------------------------------
void Vertex::AddNeighbour(Vertex* neighbour, bool silentMode)
{
	if (ValidNeighbour(neighbour->Name()) == false)
	{
		string str = "Error: Vertex " + neighbour->PrintName();
		str += " is not a valid neighbour of vertex " + this->PrintName();
		Debug::PrintDebugMsg(str);
		return;
	}
	set<VertexKey >::iterator it = m_NeighboursInGraph.find(neighbour->Name());
	if (it == m_NeighboursInGraph.end())
	{ // if the vertex doesn't already exist in the set - add it
		m_NeighboursInGraph.insert(m_NeighboursInGraph.begin(), neighbour->Name());
		m_Rank++;
	}
	else
		if (!silentMode)
		{
			string str = "Warning: Vertex " + neighbour->PrintName(); 
			str += " was already a neighbour of vertex " + this->PrintName();
			str += " in the graph";
			Debug::PrintDebugMsg(str);
		}
	it = m_NeighboursNotInGraph.find(neighbour->Name());
	if (it == m_NeighboursNotInGraph.end())
	{ // if the neighbour isn't in the neighbours not in graph set - report error
		if (!silentMode)
		{
			string str = "Warning: Vertex " + neighbour->PrintName(); 
			str +=	" not a neighbour of vertex " + this->PrintName();
			str +=  " not in the graph";
			Debug::PrintDebugMsg(str);
		}
		return;
	}
	m_NeighboursNotInGraph.erase(it);
}	

//-----------------------------------------------------------------------------------------
// GetNeighboursInGraph: returns a set of all the vertex's neighbours that are still in the graph
//-----------------------------------------------------------------------------------------
set<VertexKey > Vertex::GetNeighboursInGraph()
{
	return m_NeighboursInGraph;
}

//-----------------------------------------------------------------------------------------
// GetNeighboursNotInGraph: returns a set of all the vertex's neighbours that are not in the graph
//-----------------------------------------------------------------------------------------
set<VertexKey > Vertex::GetNeighboursNotInGraph()
{
	return m_NeighboursNotInGraph;
}

//-----------------------------------------------------------------------------------------
// GetNameFromArray: returns a VertexKey name from a vector<int> name for initialization
//-----------------------------------------------------------------------------------------
VertexKey Vertex::GetNameFromArray(bool* ar, int n)
{
	VertexKey name_bool(ar, ar+n);
	return name_bool;
}

//-----------------------------------------------------------------------------------------
// GetCombinedRank: Returns the combined rank of 2 vertices
// Parameters:
// other - other vertex
//-----------------------------------------------------------------------------------------
int Vertex::GetCombinedRank(Vertex* other)
{
	int totalRank = Rank();

	set<VertexKey >::iterator it; 
	set<VertexKey> otherNeigbours = other->GetNeighboursInGraph();
	// Go over all of the other vertex neighbors in the graph. Add 1 to combined rank for each one
	// that isn't a neighbor in the graph for this vertex (it's in the graph, so it can't be a neighbor
	// not in the graph).
	for (it = otherNeigbours.begin(); it != otherNeigbours.end(); it++)
	{	
		Vertex *v = GetVertexFromRightDirectory(*it);
		
		if (!NeighboursInGraph(v))
		{
			totalRank++;
		}
	}

	return totalRank;
}

//-----------------------------------------------------------------------------------------
// Private
//-----------------------------------------------------------------------------------------

//-----------------------------------------------------------------------------------------
// CreateNeighbours: this method creates all the neighbours of the vertex. It is private since it is used
// only in the vertex constructor
//-----------------------------------------------------------------------------------------
void Vertex::CreateNeighbours()
{
	VertexKey neighbourName = m_VertexName; // will differ from m_VertexName in 2 coordinates
	unsigned int size = m_VertexName.size();
	for (unsigned int i=0; i<size; i++)
	{
		for (unsigned int j=0; j<i; j++)
		{
			// set the apropriate coordinates in the neighbour's name
			neighbourName = m_VertexName;
			neighbourName[i] = !(m_VertexName[i]);
			neighbourName[j] = !(m_VertexName[j]);
			// if this is a valid vertex..
			if (CalcWeight(neighbourName) == m_VertexWeight)
			{
				// ..add it to the vertex in the graph set (apon creation, all vertices are in the graph)
				m_NeighboursInGraph.insert(neighbourName);
				m_Rank++;
			}
		}
	}
}

//-----------------------------------------------------------------------------------------
// ValidNeighbour: this method is used in order to check that otherVertex is indead a logical neighbour of this vertex (meaning
// they differ in exactly 2 coordinates)
//-----------------------------------------------------------------------------------------
bool Vertex::ValidNeighbour(VertexKey otherVertex)
{
	vector<int>::size_type size = m_VertexName.size();
	int counter = 0;
	for (unsigned int i=0; i<size; i++)
	{
		if (m_VertexName[i] != otherVertex[i])
		{
			counter++;
			if (counter > 2) //more then 2 coordinates are different
			{
				return false;
			}
		}
	}
	if (counter == 2) 
	{
		return true; // vectors differ in exactly 2 coordinates
	}
	return false;
}

//-----------------------------------------------------------------------------------------
// CalcWeight: calculates how many 1's there are in the vertex name
//-----------------------------------------------------------------------------------------
int Vertex::CalcWeight(VertexKey name)
{
	vector<int>::size_type size = name.size();
	int counter = 0;
	for (unsigned int i=0; i<size; i++)
	{
		if (name[i] == true)
		{
			counter++;
		}
	}
	return counter;
}

//-----------------------------------------------------------------------------------------
// UpdateNeighbours: this method is used when moving a vertex between containers: if the vertex is moved from
// the graph to a group or visa-versa it should update all its neighbours about its status change
// which is done in this method
// SetToUpdate is the set of neighbours whose entries will be updated
// inGraph marks the current status of the vertex: inGraph == true means the vertex was inserted
// to the graph, so its neighbours' lists will be updated: the "in graph" list will contain this
// vertex and the "not in graph" list will *not*
//-----------------------------------------------------------------------------------------
void Vertex::UpdateNeighbours(bool inGraph, set<VertexKey > SetToUpdated)
{
	//update all the neighbours in the graph
	set<VertexKey >::iterator it;
	for ( it=SetToUpdated.begin() ; it != SetToUpdated.end(); it++ )
	{
		Vertex *neighbour = GetVertexFromRightDirectory(*it);
		
		if (neighbour == NULL)
		{
			Debug::PrintDebugMsg("Warning: Vertex  not found in VertexDirectory ");
			continue;
		}
		// if this vertex is currently in the graph
		if (inGraph == true)
		{
			// add this vertex to the neighbours' "in the graph" list and remove it from the "not in graph" list
			neighbour->AddNeighbour(this);
		}
		else // this vertex is now in a group (*not* in the graph)
		{
			neighbour->RemoveNeighbour(this);
		}
	}
}



//-----------------------------------------------------------------------------------------
// GetAllRelatedInterchangeables: Returns all interchangeable vertices that can be replaced
//                                by neighbours in the graph of this vertex
//-----------------------------------------------------------------------------------------
set<Vertex*> Vertex::GetAllRelatedInterchangeables()
{
	set<Vertex*> result;
	set<VertexKey>::iterator it;
	for (it = m_NeighboursInGraph.begin(); it != m_NeighboursInGraph.end(); it++)
	{

		Vertex *neighbour = GetVertexFromRightDirectory(*it);
		// If this neighbour is a replacement, add all of it's interchangeables
		if (neighbour->IsReplacement())
		{
			set<VertexKey>::iterator interIt;
			set<VertexKey> interchangeables = neighbour->GetInterchangeables();
			for (interIt = interchangeables.begin(); interIt != interchangeables.end(); interIt++)
			{
				Vertex *relatedInterchangeable = GetVertexFromRightDirectory(*interIt);
				if (relatedInterchangeable != this && relatedInterchangeable->IsInGraph() && relatedInterchangeable->Interchangeable() && result.find(relatedInterchangeable)== result.end())
				{
					result.insert(relatedInterchangeable);
				}
			}

		}

		if (neighbour->Interchangeable())
		{
			if (neighbour != this && neighbour->IsInGraph()  && result.find(neighbour)== result.end())
			{
				result.insert(neighbour);
			}
		}
	}

	return result;
}



//-----------------------------------------------------------------------------------------
// CanWholeListBeReplaced: Tries to replace the whole list of interchangeables and returns
//                         true if they all can be replaced or returned to original groups
//-----------------------------------------------------------------------------------------
bool Vertex::CanWholeListBeReplaced(set<Vertex*> interchangeables)
{
	if (interchangeables.empty())
	{
		return true;
	}

	// Get and remove front element
	Vertex *currentInterchangeable = *(interchangeables.begin());
	interchangeables.erase(interchangeables.begin());

	bool replace = false;
	bool returnToGroup = false;
	if (currentInterchangeable->CanReturnToOriginalGroup())
	{
		returnToGroup = true;
	}

	if (!returnToGroup && currentInterchangeable->CanBeReplaced())
	{
		replace = true;
	}

	bool canBeReplaced =  returnToGroup || replace;

	if (canBeReplaced)
	{
		RankSet *rankSet = NULL; 
		Vertex *replacement;
		Graph *graph = currentInterchangeable->GetContainingGraph();
		bool replacementInGraph = true;
		if (returnToGroup)
		{
			graph->RemoveVertex(currentInterchangeable);
			// Return vertex to original group but do not erase all lists
			Debug::PrintDebugMsg("Checking "+currentInterchangeable->PrintName()+ ": returning to group");
			currentInterchangeable->ReturnToOriginalContainer(false);
		} else
		{
			replacement = currentInterchangeable->GetLegalReplacementVertex();
			if (replacement == NULL)
			{
				return false;
			}
			replacementInGraph = replacement->IsInGraph();
			if (graph->IsVertexInGraph(replacement))
			{
				graph->RemoveVertex(replacement);
				// try to replace this vertex
				Debug::PrintDebugMsg("Checking "+currentInterchangeable->PrintName()+ ": replacing with "+replacement->PrintName());
				currentInterchangeable->ReplaceWith(replacement, graph, false);
			}
			else
			{
				Debug::PrintDebugMsg("replacement chosen is not in graph");
				return false;
			}
			

		}
		canBeReplaced = CanWholeListBeReplaced(interchangeables);

		// Clean up
		// If we retuned the vertex to the group, put in back in the graph
		if (returnToGroup)
		{
			Group *group = dynamic_cast<Group*>(currentInterchangeable->GetPreviousContainer());
			if (group == NULL)
			{
				throw new GraphColoringException("Interchangeable has no original group");
			}
			group->RemoveVertex(currentInterchangeable);
			graph->InsertVertex(currentInterchangeable);
			Debug::PrintDebugMsg(currentInterchangeable->PrintName()+" is back in graph and not group");
			currentInterchangeable->SetInterchangeableFlag(true);
		} else
		{
			// Undo replacement
			replacement->UndoReplacementWith(currentInterchangeable, replacementInGraph);
		}
	}

	return canBeReplaced;
}


//-----------------------------------------------------------------------------------------
// GetVertexFromRightDirectory: Gets a vertex by name from static or current working directory
//-----------------------------------------------------------------------------------------
Vertex *Vertex::GetVertexFromRightDirectory(VertexKey name)
{
	VertexDirectory* dir = (VertexDirectory*)m_Directory;
	Vertex *v;
	if (dir == NULL)
	{	//use static directory
		v = VertexDirectory::GetStaticCopyVertex(name);
	}
	else
	{	// use the directory associated with this vertex
		v = dir->GetWorkingCopyVertex(name);
	}
	if (v == NULL)
	{
		throw(new GraphColoringException("Vertex not in in directory"));
	}

	return v;
}